package com.zp.self.module.level_4_算法练习.数据结构.数组;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author By ZengPeng
 */
public class 力扣_594_最长和谐子序列 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{1,2,-1,1,2,5,2,5,2}));
        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{1,3,5,7,9,11,13,15,17}));
        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{1,3,2,2,5,2,3,7}));
        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{1,2,3,4}));
        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{1,1,1,1}));
        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{1,2,3,3,1,-14,13,4}));
        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{3,2,2,3,2,1,3,3,3,-2,0,3,2,1,0,3,1,0,1,3,0,3,3}));
        System.out.println(new 力扣_594_最长和谐子序列().findLHS(new int[]{5,2,2,6,7,3,5,4,4,6,0,8,0,8,1,10,0,2,0,10,1,9,7,-10,3,3,2,9,9,1,5,9,1,8,1,8,0,5,8,7,6,10,5,-8,10,5,6,10,1,2,4,5,5,0,9,8,5,2,6,1,3,3,10,5,-7,0,7,0,4,2,5,10,7,7,8,0,1,0,4,0,3,1,6,10,10,7,8}));
    }

    /**
    题目：和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
     现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
     数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

     示例 1：
     输入：nums = [1,3,2,2,5,2,3,7]
     输出：5
     解释：最长的和谐子序列是 [3,2,2,2,3]

     示例 2：
     输入：nums = [1,2,3,4]
     输出：2

     示例 3：
     输入：nums = [1,1,1,1]
     输出：0

    分析：【P 💔💔🖤🖤】
       1.双循环: 两个计数器less:记录小于当前值的数据和，more:记录大于当前值的和
            优化剪枝：nums[i]是否已经出现过了？ 跳过
                    max > len-1 ？返回
        -- 执行用时：1133 ms, 在所有 Java 提交中击败了5.04%的用户 【有点失败:开始以为不能排序】

     大神:快速排序O(n*logn) + 双指针O(n)  -- 好他妈绕的双指针
        -- 执行用时：13 ms, 在所有 Java 提交中击败了98.39%的用户
     大神：map存储每个值的个数  然后相加大于此数的值

    边界值 & 注意点：
       1.案例：[1,2,3,3,1,-14,13,4 ]  错误原因：跳太快了  要3指针才行
       2.案例：[3,2,2,3,2,1,3,3,3,-2,0,3,2,1,0,3,1,0,1,3,0,3,3]   错误原因：
     **/
    public int findLHS(int[] nums) {
        //大神代码：
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        for (int i = 0, j = 0; j < n; j++) {
            while (i < j && nums[j] - nums[i] > 1)
                i++;
            if (nums[j] - nums[i] == 1)
                ans = Math.max(ans, j - i + 1);
        }
        return ans;


        //大神:快速排序O(n*logn) + 双指针O(n)
       /* Arrays.sort(nums);
        int left=0,right=0,target=nums[0]+1,max=0;
        while (++right<nums.length){
           if(nums[right]==target+1){
              if(nums[right-1] ==target){
                  max = Math.max(max,right-left);
                  while (nums[left]!=target)
                      left++;
              }else
                  left=right;
               target=nums[left]+1;
           }else  if(nums[right]>target+1){
               if(nums[right-1] ==target) {
                   max = Math.max(max, right - left);
               }
               left = right;
               target=nums[left]+1;
           }
        }
        if(nums[right-1]==target)
            max = Math.max(max,right-left);
        return max;
*/
        // 1.双循环: 两个计数器less:记录小于当前值的数据和，more:记录大于当前值的和  -----有点垃圾啦
        /*int less=1,more=1,max=0,len=nums.length;
        boolean haveLess=false,haveMore=false;
        Set<Integer> have = new HashSet<>();
        for (int i = 0; i < len; i++) {
            if(max>len-i) return max; // max > len-1 ？返回
            if(have.contains(nums[i])) continue;//nums[i]是否已经出现过了？ 跳过
            have.add(nums[i]);
            for (int j = i+1; j < len; j++) {
                if(nums[i]==nums[j]){
                    less++;more++;
                }else if(nums[i] +1==nums[j]){
                    haveLess =true;
                    less++;
                }else if(nums[i] ==nums[j]+1){
                    haveMore=true;
                    more++;
                }
            }
            if(less!=1 && haveLess)
                max=Math.max(max,less);
            if(more!=1 && haveMore)
                max=Math.max(max,more);
            less=1;more=1;haveLess=false;haveMore=false;
        }
        return max;*/
    }
}
